package leetcode

/*
 * @lc app=leetcode.cn id=206 lang=golang
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 栈
func reverseList2(head *ListNode) *ListNode {
	stack := make([]int, 0)
	for node := head; node != nil; node = node.Next {
		stack = append(stack, node.Val)
	}

	newHead := &ListNode{}
	node := newHead
	for i := len(stack) - 1; i >= 0; i-- {
		node.Next = &ListNode{Val: stack[i]}
		node = node.Next
	}
	return newHead.Next
}

// 递归
func reverseList3(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	var newHead *ListNode
	var recursion func(*ListNode) *ListNode
	recursion = func(node *ListNode) *ListNode {
		// newNode := &ListNode{Val: node.Val}
		if node.Next == nil {
			newHead = node
		} else {
			pre := recursion(node.Next)
			pre.Next = node
		}
		return node
	}
	recursion(head)
	head.Next = nil
	return newHead
}

// 官方-递归
func reverseList4(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}

// 官方-迭代
func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	for curr := head; curr != nil; {
		prev, curr.Next, curr = curr, prev, curr.Next
	}
	return prev
}

// @lc code=end
